package com.leetcode;

import com.leetcode.common.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 面试题 04.06. 后继者
 * 中序遍历
 * 2022-05-16 每日一题
 *
 * @author fy
 * @date 2022-05-16 22:22
 */
public class Solution04_06 {

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode prev = null;
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if (prev == p) {
                return cur;
            }
            prev = cur;
            cur = cur.right;
        }
        return null;
    }

}
